package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 63. 不同路径 II
 * @date 2025/5/12 11:59
 */
public class E63 {

    private int count;

    /**
     * 方法一：回溯
     *
     * @param obstacleGrid 网格
     * @return 路径数
     */
    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        int[][] directions = {{0, 1}, {1, 0}};
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[n - 1][m - 1] == 1)
            return 0;
        dfs(obstacleGrid, directions, 0, 0, n, m);
        return count;
    }

    /**
     * 回溯
     *
     * @param obstacleGrid 网格
     * @param directions   方向
     * @param i            当前行
     * @param j            当前列
     * @param n            行数
     * @param m            列数
     */
    private void dfs(int[][] obstacleGrid,
                     int[][] directions,
                     int i, int j,
                     int n, int m) {
        if (i == n - 1 && j == m - 1) {
            count++;
            return;
        }
        for (int k = 0; k < 2; k++) {
            int newI = i + directions[k][0];
            int newJ = j + directions[k][1];
            if (0 <= newI && newI < n && 0 <= newJ && newJ < m && obstacleGrid[newI][newJ] != 1) {
                dfs(obstacleGrid, directions, newI, newJ, n, m);
            }
        }
    }

    /**
     * 方法二：动态规划
     *
     * @param obstacleGrid 网格
     * @return 路径数
     */
    public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[][] dp = new int[n + 1][m + 1];
        dp[1][1] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i == 1 && j == 1) continue;
                if (obstacleGrid[i - 1][j - 1] == 1) dp[i][j] = 0;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n][m];
    }
}
